package org.example.leetcode;

import java.util.Arrays;

/**
 * @author: lynn
 * @Descript: https://www.bilibili.com/video/BV1N4411V7Yw?from=search&seid=1911956948003553806
 * @Descript: 下一个排列
 * @date: 2021/8/1 18:26
 * @version: 1.0
 */
public class LC31 {
    public static void main(String[] args) {
        LC31 lc=new LC31();
        int[] nums={1,2,5,8,8,7,7};
        lc.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

    }
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        int i=n-2;
        //找出下一位 1 2 2 2 3 1
        while (i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        //i=n-2,
        if (i>=0){
            int j=n-1;
            //fixme 考虑重复的场景
            while (j>i && nums[j]<=nums[i]){ //这种情况下nums[j] 一定小于等于 nums[i]
                j--;
            }
            swap(nums,i,j);
        }

        //swap之后是  1 2 2 3 2 1
        reverse(nums,i+1,n-1); //对调 i 之后的， 2,1 对调为 1,2
    }
    private void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    //fixme 不断地把前后两个数进行swap
    private void reverse(int[] nums,int lo,int hi){
        while(lo<hi){
            //fixme 每次都进行前后两个数swap，然后进行++，或者--
            swap(nums,lo++,hi--);
        }
    }
}
